#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/2/27 10:21
# ===========================================
#       题目名称： 18. 四数之和
#       题目地址： https://leetcode.cn/problems/4sum/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================


class Solution:

    def fourSum(self, nums, target):
        # 1. 判断长度是否小于4
        if len(nums) < 4:
            return []
        # 2. 排序
        nums.sort()
        # 3. 排除 超过 4个的 0  和 超过3个的相同元素
        p = 3
        while p < len(nums):
            if nums.count(nums[p]) > 4:
                del nums[p]
            p += 1
        print(nums)
        # 4. 定义返回值
        setRes = set()

        import time
        s1 = time.time()

        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    for l in range(k + 1, len(nums)):
                        tmp = nums[i] + nums[j] + nums[k] + nums[l]
                        if target < tmp:       # 核心提速代码
                            break
                        if target == tmp:
                            setRes.add((nums[i], nums[j], nums[k], nums[l]))
                            break
        print(time.time() - s1)
        return list([list(res) for res in setRes])

    def fourSum3(self, nums, target):
        """
            时间超限
        """
        # 1. 判断长度是否小于4
        if len(nums) < 4:
            return []
        # 2. 排序
        nums.sort()
        # 3. 排除 超过 4个的 0  和 超过3个的相同元素
        p = 3
        while p < len(nums):
            if nums.count(nums[p]) > 4:
                del nums[p]
            p += 1
        print(nums)
        # 4. 定义返回值
        setRes = set()
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                for k in range(j + 1, len(nums)):
                    for l in range(k + 1, len(nums)):
                        if target == nums[i] + nums[j] + nums[k] + nums[l]:
                            setRes.add((nums[i], nums[j], nums[k], nums[l]))
                            break
        return list([list(res) for res in setRes])

    def fourSum2(self, nums, target):
        """
            时间超限
        """
        # 1. 判断长度是否小于4
        if len(nums) < 4:
            return []
        # 2. 排序
        nums.sort()
        # 3. 判断重复元素超过4个的 剔除
        if len(nums) > 4:
            # 获取指针
            p = 4
            while p < len(nums):
                if nums[p] == nums[p - 1] == nums[p - 2] == nums[p - 3] == nums[p - 4]:
                    del nums[p]
                else:
                    p += 1
        # 4. 定义变量开始求和
        i, j, k, l, setRes = 0, 1, 2, len(nums) - 1, set()
        print(nums)
        while i < j < k < l:
            val = target - (nums[i] + nums[j])
            while k < l:
                while k < l:
                    print(i, j, k, l)
                    tmp = val - (nums[k] + nums[l])
                    if tmp == 0:
                        setRes.add((nums[i], nums[j], nums[k], nums[l]))
                        break
                    l -= 1
                l = len(nums) - 1
                k += 1
            if j + 1 <= len(nums) - 3:
                j += 1
                k = j + 1
                l = len(nums) - 1
            else:
                if i + 1 <= len(nums) - 4:
                    i += 1
                    j = i + 1
                    k = j + 1
                    l = len(nums) - 1
                else:
                    break

        return list([list(res) for res in setRes])

    def fourSumXXX(self, nums, target):
        """
            别人的思路
        """
        nums.sort()
        n = len(nums)
        res = []
        p = 0  # p, k, i, j
        while p < n - 3:  # 文中提到的条件1和条件2，可以直接跳过
            if nums[p] + 3 * nums[p + 1] > target: break
            if nums[p] + 3 * nums[-1] < target:
                while p < n - 4 and nums[p] == nums[p + 1]: p += 1
                p += 1
                continue
            k = p + 1
            while k < n - 2:  # k 和 p 的判断是一样的
                if nums[p] + nums[k] + 2 * nums[k + 1] > target: break
                if nums[p] + nums[k] + 2 * nums[-1] < target:
                    while k < n - 3 and nums[k] == nums[k + 1]:
                        k += 1
                    k += 1
                    continue
                i = k + 1
                j = n - 1
                new_target = target - nums[p] - nums[k]
                while i < j:
                    if nums[i] + nums[j] > new_target:
                        j -= 1
                    elif nums[i] + nums[j] < new_target:
                        i += 1
                    else:
                        res.append([nums[p], nums[k], nums[i], nums[j]])
                        i += 1
                        j -= 1
                        while i < j and nums[i] == nums[i - 1]: i += 1  # 避免结果重复
                        while i < j and nums[j] == nums[j + 1]: j -= 1  # 避免结果重复
                while k < n - 3 and nums[k] == nums[k + 1]: k += 1
                k += 1
            while p < n - 4 and nums[p] == nums[p + 1]: p += 1
            p += 1
        return res


if __name__ == "__main__":
    s = Solution()
    print("nums = [1,0,-1,0,-2,2], target = 0 =>" + str(
        s.fourSum(nums=[1, 0, -1, 0, -2, 2], target=0)))  # [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
    print("nums = [2,2,2,2,2], target = 8 =>" + str(s.fourSum(nums=[2, 2, 2, 2, 2], target=8)))  # [[2,2,2,2]]
    print("nums = [-1,0,1,2,-1,-4], target = -1 =>" + str(
        s.fourSum(nums=[-1, 0, 1, 2, -1, -4], target=-1)))  # [[-4,0,1,2],[-1,-1,0,1]]
    print("nums = [0,0,0,0], target = 0 =>" + str(
        s.fourSum(nums=[0, 0, 0, 0], target=0)))  # [[0,0,0,0]]
    print("nums = [-4,-3,-2,-1,0,0,1,2,3,4], target = 0 =>" + str(
        s.fourSum(nums=[-4, -3, -2, -1, 0, 0, 1, 2, 3, 4],
                  target=0)))  # [[-4,-3,3,4],[-4,-2,2,4],[-4,-1,1,4],[-4,-1,2,3],[-4,0,0,4],[-4,0,1,3],[-3,-2,1,4],
    # [-3,-2,2,3],[-3,-1,0,4],[-3,-1,1,3],[-3,0,0,3],[-3,0,1,2],[-2,-1,0,3],[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

    print("-----, target = -236727523 =>" + str(
        s.fourSum(
            nums=[91277418, 66271374, 38763793, 4092006, 11415077, 60468277, 1122637, 72398035, -62267800, 22082642,
                  60359529, -16540633, 92671879, -64462734, -55855043, -40899846, 88007957, -57387813, -49552230,
                  -96789394, 18318594, -3246760, -44346548, -21370279, 42493875, 25185969, 83216261, -70078020,
                  -53687927, -76072023, -65863359, -61708176, -29175835, 85675811, -80575807, -92211746, 44755622,
                  -23368379, 23619674, -749263, -40707953, -68966953, 72694581, -52328726, -78618474, 40958224,
                  -2921736, -55902268, -74278762, 63342010, 29076029, 58781716, 56045007, -67966567, -79405127,
                  -45778231, -47167435, 1586413, -58822903, -51277270, 87348634, -86955956, -47418266, 74884315,
                  -36952674, -29067969, -98812826, -44893101, -22516153, -34522513, 34091871, -79583480, 47562301,
                  6154068, 87601405, -48859327, -2183204, 17736781, 31189878, -23814871, -35880166, 39204002,
                  93248899, -42067196, -49473145, -75235452, -61923200, 64824322, -88505198, 20903451, -80926102,
                  56089387, -58094433, 37743524, -71480010, -14975982, 19473982, 47085913, -90793462, -33520678,
                  70775566, -76347995, -16091435, 94700640, 17183454, 85735982, 90399615, -86251609, -68167910,
                  -95327478, 90586275, -99524469, 16999817, 27815883, -88279865, 53092631, 75125438, 44270568,
                  -23129316, -846252, -59608044, 90938699, 80923976, 3534451, 6218186, 41256179, -9165388,
                  -11897463, 92423776, -38991231, -6082654, 92275443, 74040861, 77457712, -80549965, -42515693,
                  69918944, -95198414, 15677446, -52451179, -50111167, -23732840, 39520751, -90474508, -27860023,
                  65164540, 26582346, -20183515, 99018741, -2826130, -28461563, -24759460, -83828963, -1739800,
                  71207113, 26434787, 52931083, -33111208, 38314304, -29429107, -5567826, -5149750, 9582750,
                  85289753, 75490866, -93202942, -85974081, 7365682, -42953023, 21825824, 68329208, -87994788,
                  3460985, 18744871, -49724457, -12982362, -47800372, 39958829, -95981751, -71017359, -18397211,
                  27941418, -34699076, 74174334, 96928957, 44328607, 49293516, -39034828, 5945763, -47046163,
                  10986423, 63478877, 30677010, -21202664, -86235407, 3164123, 8956697, -9003909, -18929014,
                  -73824245], target=-236727523)))
